The Adaptive Multilevel Splitting algorithm is a very powerful and versatilemethod to estimate rare events probabilities. It is an iterative procedure onan interacting particle system, where at each step, the $k$ less well-adaptedparticles among $n$ are killed while $k$ new better adapted particles areresampled according to a conditional law. We analyze the algorithm in theidealized setting of an exact resampling and prove that the estimator of therare event probability is unbiased whatever $k$. We also obtain a preciseasymptotic expansion for the variance of the estimator and the cost of thealgorithm in the large $n$ limit, for a fixed $k$.
展开▼
机译:自适应多级拆分算法是一种非常强大且用途广泛的方法,可以估算罕见事件的概率。这是在相互作用的粒子系统上进行的迭代过程,其中在每个步骤中,将杀死$ n $中适应性较差的$ k $粒子,而根据条件法则对$ k $适应性更好的新粒子进行重新采样。我们在精确重采样的理想化设置下分析了该算法,并证明了无论$ k $,稀有事件概率的估计量都是无偏的。对于固定的$ k $,我们还获得了一个精确的渐近展开式,该估计量的方差和算法的成本在较大的$ n $限制内。
展开▼